class Solution
{
public:
    int numRollsToTarget(int n, int k, int target)
    {
        vector<int> dpLast(target + 1, 0);
        for (int i = 1; i <= min(k, target); ++i)
        {
            dpLast[i] = 1;
        }

        for (int _ = 1; _ < n; ++_)
        {
            vector<int> dpNew(target + 1, 0);
            for (int t = 0; t <= target; ++t)
            {
                for (int d = 1; d <= k; ++d)
                {
                    if (t - d >= 0)
                    {
                        dpNew[t] += dpLast[t - d];
                        dpNew[t] %= 1000000007;
                    }
                }
            }
            dpNew.swap(dpLast);
        }
        return dpLast[target];
    }
};